An associative array, map, symbol table, or dictionary is an abstract data type that generally includes a collection of key-value pairs, such that each possible key appears just once in the collection. A key value store is a type of computer database that can be used in data-intensive, high-performance, scale-out computing environments. Key value stores allow computer applications to store schema-less data. Schema-less data can include structures having a string that represents the key and the actual data that is considered the value in a “key-value” relationship. Such key-value structures replace the need for fixed data models and also allow for proper formatting.
Traditionally key value stores consider a flash memory device or a solid state disk/drive (SDD) as a block device. Thus, a key value store maintains its own mapping or index which, in many cases, can be redundant to mappings maintained by a Flash Translation Layer (FTL) of the flash memory or SDD. Conventionally, the mapping maintained in the system memory by the key value store includes the actual key. This is needed to check for hash collisions and key over-write scenarios. Often keeping all of the keys in memory requires significant memory. In one example, the key value index may include a hash of the keys that is efficiently traversable or searchable. A key value index may be stored in binary search tree or in a data structure specialized to a particular type of keys.
While key value stores traditionally make use of strings as keys any data form is possible. The general limitation of key values stores is that the relationship between keys and values be one-to-one. That is to say that each key is associated with one and only one value, and each value is associated with one and only one key.